package com.wc.算法基础课.D第四讲数学知识.快速幂.互质数的个数;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/2 0:15
 * @description https://www.acwing.com/problem/content/4971/
 */
public class Main {
    static Scanner sc = new Scanner(System.in);
    static int P = 998244353;
    static long a, b;

    public static void main(String[] args) {
        a = sc.nextInt();
        if (a == 1) {
            System.out.println(0);
            return;
        }
        b = sc.nextLong();
        long res = a;
        long n = a;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) res = res / n * (n - 1);
        System.out.println(res * qkm(a, b - 1) % P);
    }

    static long qkm(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }

        return res;
    }
}
